package lsl.LinkedList;

import java.util.Stack;

/**
 * 新数据直接添加在链表的尾部
 *
 * @author Zed
 * @date 2021/12/21 21:10
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(5, "橘右京", "橘子");
        HeroNode hero6 = new HeroNode(6, "刘备", "刘皇叔");

        //创建单链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        /*
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        */

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero6);

        // 测试一下单链表的反转功能
        /*
        System.out.println("原来链表的情况~~");
        singleLinkedList.list();
        System.out.println("倒数第k个节点~~");
        System.out.println(findLastIndexNode(singleLinkedList.getHead(), 2));
        */


        //测试修改节点的代码
        /*
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();
        */

        //测试删除节点的代码
        /*
        singleLinkedList.delete(2);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();
        */


        System.out.println("原来链表的情况~~");
        singleLinkedList.list();

        //测试一下单链表的反转功能
       /*
       System.out.println("反转单链表~~");
       reverseList(singleLinkedList.getHead());
       singleLinkedList.list();
        */
        System.out.println("倒序打印~~");
        reverseList(singleLinkedList.getHead());
        // reversePrintByStack(singleLinkedList.getHead());
    }

    //新浪面试题：获取单链表倒数第k个节点
    public static HeroNode findLastIndexNode(HeroNode head, int k) {
        //先判空
        if (head.next == null) {
            System.out.println("链表为空");
            return null;
        }
        //1.先获取有效节点个数
        int length = getLinkedListLength(head);
        if (k < 0 || k > length) {
            System.out.println("该节点不存在");
            return null;
        }
        //2.使用一个临时存储节点
        HeroNode temp = head.next;
        //3.遍历单链表
        for (int i = 0; i < length - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //腾讯面试题：将单链表反转
    public static void reverseList(HeroNode head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        HeroNode pre = null;
        HeroNode next;// 指向当前节点[cur]的下一个节点
        while (head != null) {
            //1.预留下一个节点的值  当head为2时,next=3
            next = head.next;
            //2.让当前节点的前指针指向前面的节点 把2节点的前指针指向1节点
            head.next = pre;
            //3.预留当前节点作为前指针指向的节点 把2节点预留为3节点前指针指向的值
            pre = head;
            //4.让head节点到下一个
            head = next;
        }
    }

    //百度面试题：单链表倒序打印 可以利用栈先进后出的特点
    public static void reversePrintByStack(HeroNode head) {
        if (head.next == null) {
            //链表为空 不打印
            return;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = head.next;

        while (true) {
            if (temp == null) {
                break;
            }
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    //获取单链表中有效节点个数
    public static int getLinkedListLength(HeroNode head) {
        //空链表
        if (head.next == null) {
            return 0;
        }
        //先排除头结点
        HeroNode temp = head.next;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
}


/**
 * 单链表
 */
class SingleLinkedList {
    //先初始化一个头节点, 头节点不要动, 不存放具体的数据
    private static HeroNode head = new HeroNode(0, "", "");

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next 指向 新的节点
    //3. 新增的节点都是在最后
    public void add(HeroNode heroNode) {
        //1.因为头结点不存放数据 所有需要一个辅助变量temp来存放数据
        HeroNode temp = head;
        //循环判断该链表是否到了最后一个节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    //第二种方式：根据英雄排名将英雄添加到指定位置
    public void addByOrder(HeroNode heroNode) {
        //1.因为头结点不存放数据 所有需要一个辅助变量temp来存放数据
        HeroNode temp = head;
        //2.加一个作为链表判断的开关
        Boolean flag = false;
        while (true) {
            /**
             * 链表退出循环遍历比较的情况
             * 1.链表已经在链表尾了
             * 2.满足插入条件
             * 3.新插入的数据排名已经有了
             */
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            //后移，遍历当前链表
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
        } else {
            //此时将新插入节点的next设置为原节点temp的next
            heroNode.next = temp.next;
            //temp.next为新插入的节点数据
            temp.next = heroNode;
        }
    }

    public void update(HeroNode newHeroNode) {
        //1.因为头结点不存放数据 所有需要一个辅助变量temp来存放数据
        HeroNode temp = head;
        //2.加一个作为链表判断的开关
        Boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
        }
    }

    public void delete(int no) {
        //1.因为头结点不存放数据 所有需要一个辅助变量temp来存放数据
        HeroNode temp = head;
        //2.加一个作为链表判断的开关
        Boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //说明到了链表尾部 没有数据了
                break;
            }
            //说明找到了待删除节点的上个节点
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            //链表后移
            temp = temp.next;
        }
        if (flag) {
            //删除节点
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }

    //获取头结点
    public HeroNode getHead() {
        return head;
    }

    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //使用一个辅助变量temp来存放数据进行比较
        HeroNode temp = head.next;
        while (true) {
            //当temp为null说明到了链表尾部
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

//定义HeroNode,每个HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    //为了显示方法，我们重新toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }
}
